// https://leetcode-cn.com/problems/perfect-squares/submissions/
// 完全背包的最值问题
class Solution {
public:
    int numSquares(int n) {
        vector<int> rec(n + 1, n);
        int m = sqrt(n);
        // rec[1] = 1; //千万别忘了初始化！！！ 12 1 2 3 4 2 3 4 5 3 2 3 4 
        rec[0] = 0; //0 1 2 3 1 2 3 4 2 1 2 3 3 注意从0开始初始化！rec[j - tmp]可以取到0。上面的初始化导致rec[0]不对，所以这边4就没法用2*2更新了。
        for (int i = 1; i <= m; ++i) {
            int tmp = i * i;
            for (int j = tmp; j <= n; ++j) {
                rec[j] = min(rec[j], rec[j - tmp] + 1);
            }
        }
        return rec.back();
    }
};